package qjc.h_二叉树;

import com.二叉树.练习题.TreeNode;

public class h14_二叉树的最近公共祖先 {
    /**
     * 解题思路：
     * 本题要求在二叉树中找到两个指定节点 p 和 q 的最近公共祖先（LCA）。
     * 使用递归后序遍历（左右根）的思路：
     * <p>
     * 1. 从根节点开始向下搜索，递归处理左右子树；
     * 2. 如果当前节点是 null、p 或 q，直接返回该节点（作为递归终止条件）；
     * 3. 在左右子树中分别查找 p 和 q：
     * - 若 p 和 q 分别位于左右子树，则当前根节点就是最近公共祖先；
     * - 若只在某一侧找到，则该侧返回的节点为最近公共祖先；
     * - 若都未找到，返回 null。
     * <p>
     * 核心思想：利用递归回溯，自底向上判断路径交汇点，第一个同时包含 p 和 q 的节点即为 LCA。
     * 时间复杂度 O(n)，空间复杂度 O(h)（h 为树高，递归栈深度）。
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        return left == null ? right : left;
    }
}
